//
// Created by francklinson on 2021/7/31 AT 21:55.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime(i))
                ++ans;
        }
        return ans;
    }

    bool isPrime(int n) {
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
};

class Solution2 {
public:
    int countPrimes(int n) {
        // 埃式筛 质数的倍数都是非质数
        vector<int> isPrime(n, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                ans += 1;
                if ((long long) i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
};


int main() {
    Solution2 solution;
    cout << solution.countPrimes(1500000) << endl;
    return 0;
}

